package com.jwetherell.algorithms.strings;

import java.util.BitSet;
import java.util.StringTokenizer;

public class StringFunctions {

    private static final char SPACE = ' ';

    public static final String reverseWithStringConcat(String string) {
        String output = new String();
        for (int i = (string.length() - 1); i >= 0; i--) {
            output += (string.charAt(i));
        }
        return output;
    }

    public static final String reverseWithStringBuilderBuiltinMethod(String string) {
        StringBuilder builder = new StringBuilder(string);
        return builder.reverse().toString();
    }
    
    /**
     * StringBuilder is preferred over String.concat() because in String.concat()
     * every time a new string literal is created. So if you want to do concat()
     * very often then its better to use StringBuilder
     * 
     * This uses extra space equals to the number of characters in the input string
     * 
     * @param string
     * @return
     */
    public static final String reverseWithStringBuilder(String string) {
        StringBuilder builder = new StringBuilder();
        for (int i = (string.length() - 1); i >= 0; i--) {
            builder.append(string.charAt(i));
        }
        return builder.toString();
    }

    /**
     * Reverse with swaps within the same string sequence is preferred over StringBuilder
     * as it takes no extra space
     * 
     * @param string
     * @return
     */
    public static final String reverseWithSwaps(String string) {
        char[] array = string.toCharArray();
        
        int lastIndex = array.length - 1;
        int middleIndex = (int) Math.floor(array.length / 2);
        
        char tempChar;
        for (int i = lastIndex; i >= middleIndex; i--) {
            tempChar = array[lastIndex - i];
            array[lastIndex - i] = array[i];
            array[i] = tempChar;
        }
        return String.valueOf(array);
    }

    public static final String reverseWithXOR(String string) {
        char[] array = string.toCharArray();
        
        int length = array.length;
        int middleIndex = (int) Math.floor(array.length / 2);
        
        for (int i = 0; i < middleIndex; i++) {
            array[i] ^= array[length - i - 1];
            array[length - i - 1] ^= array[i];
            array[i] ^= array[length - i - 1];
        }
        
        return String.valueOf(array);
    }

    public static final String reverseWordsByCharWithAdditionalStorage(String string) {
        StringBuilder builder = new StringBuilder();

        char c = 0;
        int index = 0;
        int last = string.length();
        int lastIndex = string.length() - 1;
        
        StringBuilder temp = new StringBuilder();
        for (int i = lastIndex; i >= 0; i--) {
            c = string.charAt(i);
            if (c == SPACE || i == 0) {
                index = (i == 0) ? 0 : i + 1;
                temp.append(string.substring(index, last));
                if (index != 0)
                    temp.append(c);
                builder.append(temp);
                temp.delete(0, temp.length());
                last = i;
            }
        }

        return builder.toString();
    }

    public static final String reverseWordsUsingStringTokenizerWithAdditionalStorage(String string) {
        String output = new String();

        StringTokenizer st = new StringTokenizer(string);
        while (st.hasMoreTokens()) {
            output = (st.nextToken()) + ' ' + output;
        }

        return output;
    }

    public static final String reverseWordsUsingSplitWithAdditionalStorage(String string) {
        StringBuilder builder = new StringBuilder();

        String[] temp = string.split(" ");
        for (int i = (temp.length - 1); i >= 0; i--) {
            builder.append(temp[i]);
        }

        return builder.toString();
    }

    
    public static final String reverseWordsInPlace(String string) {
        char[] chars = string.toCharArray();

        int lengthI = 0;
        int lastI = 0;
        int lengthJ = 0;
        int lastJ = chars.length - 1;

        int i = 0;
        char iChar = 0;
        char jChar = 0;
        while (i < chars.length && i <= lastJ) {
            iChar = chars[i];
            if (iChar == SPACE) {
                lengthI = i - lastI;
                for (int j = lastJ; j >= i; j--) {
                    jChar = chars[j];
                    if (jChar == SPACE) {
                        lengthJ = lastJ - j;
                        swapWords(lastI, i - 1, j + 1, lastJ, chars);
                        lastJ = lastJ - lengthI - 1;
                        break;
                    }
                }
                lastI = lastI + lengthJ + 1;
                i = lastI;
            } else {
                i++;
            }
        }

        return String.valueOf(chars);
    }

    private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) {
        int lengthA = endA - startA + 1;
        int lengthB = endB - startB + 1;

        int smallestLength = lengthA;
        if (lengthA > lengthB)
            smallestLength = lengthB;

        int indexA = 0;
        int indexB = 0;
        char tempChar = 0;
        for (int i = 0; i < smallestLength; i++) {
            indexA = startA + i;
            indexB = startB + i;

            tempChar = array[indexB];
            array[indexB] = array[indexA];
            array[indexA] = tempChar;
        }

        if (lengthB > lengthA) {
            smallestLength = lengthB - lengthA;
            int end = 0;
            for (int i = 0; i < smallestLength; i++) {
                end = endB - ((smallestLength - 1) - i);
                tempChar = array[end];
                shiftRight(endA + i, end, array);
                array[endA + 1 + i] = tempChar;
            }
        } else if (lengthA > lengthB) {
            smallestLength = lengthA - lengthB;
            for (int i = 0; i < smallestLength; i++) {
                tempChar = array[endA];
                shiftLeft(endA, endB, array);
                array[endB + i] = tempChar;
            }
        }
    }

    private static final void shiftRight(int start, int end, char[] array) {
        for (int i = end; i > start; i--) {
            array[i] = array[i - 1];
        }
    }

    private static final void shiftLeft(int start, int end, char[] array) {
        for (int i = start; i < end; i++) {
            array[i] = array[i + 1];
        }
    }

    public static final boolean isPalindromeInPlace(String string) {
        char[] array = string.toCharArray();
        
        int lastIndex = array.length - 1;
        int middleIndex = Math.round(array.length / 2);
        char a, b;
        for (int i = lastIndex; i >= middleIndex; i--) {
            a = array[lastIndex - i];
            b = array[i];
            if (a != b)
                return false;
        }
        return true;
    }

    public static final String[] generateSubsets(String input) {
        int length = input.length();
        
        int subSetSize = (int) Math.pow(2, length);
        BitSet[] bitSets = new BitSet[subSetSize];
        String[] output = new String[subSetSize];

        for (int i = 0; i < subSetSize; i++) {
            BitSet bitSet = new BitSet(subSetSize);
            StringBuilder builder = new StringBuilder();
            if (i > 0) {
                for (int j = length - 1; j >= 0; j--) {
                    if (j == length - 1) {
                        if (i % 2 != 0)
                            bitSet.set(j, true);
                    } else {
                        boolean prev = bitSets[i - 1].get(j);
                        boolean next = true;
                        for (int k = j + 1; k < length; k++) {
                            next = next && bitSets[i - 1].get(k);
                        }
                        if (next)
                            prev = !prev;
                        bitSet.set(j, prev);
                    }
                    if (bitSet.get(j))
                        builder.append(input.charAt(j));
                }
            }
            bitSets[i] = bitSet;
            output[i] = builder.toString();
        }

        return output;
    }

    public static final int levenshteinDistance(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        int cost = 0;
        if ((sLength > 0 && tLength > 0) && sChars[0] != tChars[0])
            cost = 1;

        if (sLength == 0)
            return tLength;
        else if (tLength == 0)
            return sLength;
        else {
            int min1 = levenshteinDistance(s.substring(1), t) + 1;
            int min2 = levenshteinDistance(s, t.substring(1)) + 1;
            int min3 = levenshteinDistance(s.substring(1), t.substring(1)) + cost;

            int minOfFirstSet = Math.min(min1, min2);
            return (Math.min(minOfFirstSet, min3));
        }
    }

    public static void main(String[] args) {
//    	System.out.println(reverseWithSwaps("hello"));
//		System.out.println(reverseWordsByCharWithAdditionalStorage("hello world"));
//    	System.out.println(reverseWordsInPlace("hello world"));
    	
    	String[] subSets = generateSubsets("hello");
		for (int i = 0; i < subSets.length; i++) {
			System.out.println(i + ": " + subSets[i]);
		}
		
		System.out.println();
    	System.out.println(levenshteinDistance("hello world", "how are you"));
	}
}
